1. Field of the Invention
The present invention relates to motion estimation and particularly to a spiderweb search method for motion estimation to identify the reference macro-block.
2. Description of the Related Art
An MPEG video sequence is comprised of one or more groups of pictures, each group of which is composed of one or more pictures of type I-, P-, or B-. Intra-coded pictures, or “I-pictures,” are coded independently without reference to any other pictures. Predictive-coded pictures, or “P-pictures,” use information from preceding reference pictures, while bi-directionally predictive-coded pictures, or “B-pictures,” may use information from preceding or upcoming pictures, both, or neither.
Motion estimation is the process of estimating the displacement of a portion of an image between neighboring pictures. For example, a moving soccer ball will appear in different locations in adjacent pictures. Displacement is described as the motion vectors that give the best match between a specified region, e.g., the ball, in the current picture and the corresponding displaced region in a preceding or upcoming reference picture. The difference between the specified region in the current picture and the corresponding displaced region in the reference picture is referred to as “residue”.
In general, two known types of motion estimation methods used to estimate the motion vectors are pixel-recursive algorithms and block-matching algorithms. Pixel-recursive techniques predict the displacement of each pixel iteratively from corresponding pixels in neighboring frames. Block-matching algorithms, on the other hand, estimate the displacement between frames on a block-by-block basis and choose vectors that minimize the difference.
In conventional block-matching processes, the current image to be encoded is divided into equal-sized blocks of pixel information. In MPEG-1 and MPEG-2 video compression standards, for example, the pixels are grouped into “macro-blocks,” each consisting of a 16×16 sample array of luminance samples together with one 8×8 block of samples for each of the two chrominance components. The 16×16 array of luminance samples further comprises four 8×8 blocks that are typically used as input blocks to the compression models.
A block-matching algorithm that compares the current block to every candidate block within the search range is called a “full search”. In general, larger search areas generally produce a more accurate displacement vector, however, the computational complexity of a full search is proportional to the size of the search area and is too slow for some applications. A full search block-matching algorithm applied on a macro-block of size 16×16 pixels over a search range of ±N pixels with one pixel accuracy, for example, requires (2×N+1)2 block comparisons. For N=16, 1089 16×16 block comparisons are required. Because each block comparison requires 16×16, or 256, calculations, this method is computationally intensive and operationally very slow. Techniques that simply reduce the size of the search area, however, run a greater risk of failing to find the optimal matching block.
As a result, there has been much emphasis on producing fast algorithms for finding the matching block within a wide search range. Most fast search techniques gain speed by computing the displacement only for a sparse sampling of the full search area. The 2-D logarithmic search, for example, reduces the number of computations by computing the MSE for sparsely-spaced candidates, and then successively searching the closer spaced candidates surrounding the best candidate found in the previous iteration. In a conjugate direction search, the algorithm searches in a horizontal direction until a minimum distortion is found. Then, proceeding from that point, the algorithm searches in a vertical direction until a minimum is found. Both of these methods are faster than a full search but frequently fail to locate the optimal matching block.
Other methods for overcoming the disadvantages of a full search have employed hierarchical search techniques. In a first stage, for example, a coarse search is performed over a reasonably large area. In successive stages of a conventional hierarchical search, the size of the search area is reduced. One example of a three-step hierarchical search is described in H. M. Jong et al., “Parallel Architectures for 3-Step Hierarchical Search Block-Matching Algorithm,” IEEE Trans. On Circuits and Systems for Video Technology, Vol. 4, August 1994, pp. 407–416. The hierarchical search described in Jong et al. is inadequate for some applications because the coarse search does not utilize all of the pixel information and thus may form an incorrect starting point for the finer search.